package someTestExcemple.huaweiOd.doublepointer;

import java.util.Arrays;
import java.util.Scanner;

//https://blog.csdn.net/guorui_java/article/details/138425495
//华为OD机试 - 贪吃的猴子 - 滑动窗口（Java 2024 E卷 200分）

//todo 滑动窗口
public class GreedyMonkey {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //香蕉总串数
        int N = sc.nextInt();
        int[] arr = new int[N];
        //每串香蕉个数
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        //猴子最多能拿的香蕉串数
        int K = sc.nextInt();
        //个人的解法
        //思路：滑动窗口，窗口大小固定是k
        //在计算获取香蕉的过程中，我们模拟了一个滑动窗口，
        // 依次枚举从左边取i个香蕉时，还可以从右边取N-i个香蕉的总和。
        //其中的最大解就是答案
        //时间复杂度K*K ,,最大是N*N
        int max = 0;
        if(K>=N) {
            for (int i = 0; i < N; i++) {
                max += arr[i];
            }
            System.out.println(max);
        } else {

            //窗口大小固定是k --香蕉数组长度大于k
            //从左边开始最多可以拿K个
            for(int i=0;i<=K;i++) {
                int sum = 0;
                int left =i;
                int right = K-i;
                //左边求和
                for(int j=0;j<left;j++) {
                    sum += arr[j];
                }
                //右边求和

                //这里t的起始值不要写错
                for(int t = arr.length-right;t<arr.length;t++) {
                 sum+=arr[t];
                }
                if(sum>max) {
                    max = sum;
                }
            }
            System.out.println(max);
        }

    }
}

/**
 * 4、输入
 * 8
 * 3 5 9 3 3 4 6 6
 * 4
 *
 * 5、输出
 * 23
 */
